package ljl.alg.wangzheng_camp.round1.array_and_list;

import commons.ListNode;

public class _328_odd_even_list {
    
    /**
     * 奇数的往前放，偶数的往后放
     *
     * 需要 O(n) 时间和 O(1) 空间，就不能考虑栈、递归之类的东西了
     * 必须原地操作
     *
     * 考虑双指针，然后不停的插入
     * front end 和 p
     *
     * 这个 p 不停的往后走，来回往 head 后或 end 后插入
     *
     * 我操最后得把 front 和 end 连起来，不然就无了
     *
     * 我操居然过了
     *
     * */
    public ListNode oddEvenList2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode front = head, end = head.next, middle = end;
        ListNode p = end.next;
        boolean odd = true; // odd 去 front，非 odd 去 end
        while (p != null) {
            if (odd) {
                front.next = p;
                front = p;
            } else {
                end.next = p;
                end = p;
            }
            p = p.next;
            odd = !odd;
        }
        // 为什么不加这一行会出现环？如果奇数结尾，你后面把它连上，所以出现环了
        end.next = null;
        front.next = middle;
        return head;
    }
    
    /**
     * 秒啊他这个解法
     * */
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
        ListNode evenHead = head.next;
        ListNode odd = head, even = evenHead;
        // o e o e
        // 每次移动两个格子，后面两个都不能是 null
        // 它是 e o e o 的推进
        // 如果只有一个 e，这个 e 在上一轮已经连起来了
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
    
}
